package leetcode.solution;

import java.util.Arrays;

/**
 * 给定一个整数数组 nums ，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的最大公约数大于 1 。为了减少他的工作量，请求出最少可以切成多少个子数组。
 *
 * 示例 1：
 *
 * 输入：nums = [2,3,3,2,3,3]
 *
 * 输出：2
 *
 * 解释：最优切割为 [2,3,3,2] 和 [3,3] 。第一个子数组头尾数字的最大公约数为 2 ，第二个子数组头尾数字的最大公约数为 3 。
 *
 * 示例 2：
 *
 * 输入：nums = [2,3,5,7]
 *
 * 输出：4
 *
 * 解释：只有一种可行的切割：[2], [3], [5], [7]
 *
 * 限制：
 *
 * 1 <= nums.length <= 10^5
 * 2 <= nums[i] <= 10^6
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/qie-fen-shu-zu
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class difficult_切分数组_质数分解 {

    /**
     * f[i] 代表这个数组新增一个质数 ii 后的最少分组数。例如对于数组 [2,5,3] ，我们有 f[2] = 1, f[3] = 3, f[5] = 2f[2]=1,f[3]=3,f[5]=2, 在插入一个新的数 6 后，对于当前数组 [2,5,3,6] ，我们有 f[2] = 1, f[3] = 2, f[5] = 2f[2]=1,f[3]=2,f[5]=2 。
     *
     * 于是我们在遍历整个数组时，只要对每次遍历到的数做质因数分解，假设当前分解得到的质数为 pp ，上一次遍历的最好结果为 prevprev ，就可以做如下更新：
     *
     * f[p] = \min(f[p], prev + 1)
     * f[p]=min(f[p],prev+1)
     *
     * 其含义为当前这个数要么跟之前的某个数组成一个子数组，要么单独成一组。这样遍历下去就能高效求得答案了。
     *
     * 由于需要知道每个 nums[i]nums[i] 的所有质因子，我们需要一种方法将 nums[i]nums[i] 快速因子分解。我们用素数筛提前预处理 1 \sim 10^61∼10
     * 6
     *   内任意数字 kk 的最小质因子 min\_prime\_factor[k]min_prime_factor[k] 。获得 nums[i]nums[i] 所有质因子的方法为：
     *
     * x=nums[i]x=nums[i]
     *
     * 获取 min\_prime\_factor[x]min_prime_factor[x] 为 xx 当前的最小质因子
     *
     * x = x / min\_prime\_factor[x]x=x/min_prime_factor[x]
     *
     * 如果 x=1x=1，退出，否则回到步骤 2
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/qie-fen-shu-zu/solution/qie-fen-shu-zu-zhi-shu-shai-dp-by-leetcode-solutio/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    class Solution {

        public int splitArray(int[] nums) {
            int n = nums.length;
            int[] dp = new int[n + 1];
            int[] min = new int[(int)1e6];
            Arrays.fill(min, (int)1e6);
            for(int i = 1; i <= n; i++){
                int x = nums[i - 1];
                dp[i] = dp[i-1] + 1;
                for(int j = 2; j * j <= x; j++){
                    if(x % j != 0){
                        continue;
                    }
                    dp[i] = Math.min(dp[i], min[j] + 1);
                    min[j] = Math.min(min[j], dp[i-1]);
                    while(x % j == 0){
                        x /= j;
                    }
                }
                if(x > 1){
                    dp[i] = Math.min(dp[i], min[x] + 1);
                    min[x] = Math.min(min[x], dp[i-1]);
                }
            }
            return dp[n];
        }
    }
}
